package leetcode_zh

import (
	"go-study/src/leetcode"
)

/**
 * @Description: 206. 反转链表
 * @Keyword: 1 -> 2 -> 3 -> 4 生成新的链表
 * @Author: kami
 * @Date: 2022/5/19 13:30
 **/
func reverseList(head *leetcode.ListNode) *leetcode.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	var next = &leetcode.ListNode{
		Val: head.Val,
	}
	var res *leetcode.ListNode
	for head.Next != nil {
		head = head.Next
		res = &leetcode.ListNode{
			Val: head.Val,
		}
		res.Next = next
		next = res
	}

	return res
}

/**
 * @Description: 206. 反转链表
 * @Keyword: 1 -> 2 -> 3 -> 4 修改原
 * @Author: kami
 * @Date: 2022/5/19 13:30
 **/
func reverseListV1(head *leetcode.ListNode) *leetcode.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	var curNode = head.Next
	var nextNode = head.Next.Next
	curNode.Next = head
	head.Next = nil
	for nextNode != nil {
		var next = nextNode.Next
		nextNode.Next = curNode

		curNode = nextNode
		nextNode = next
	}

	return curNode
}

/**
 * @Description: 206. 反转链表
 * @Keyword: 1 -> 2 -> 3 -> 4 递归版本
 * @Author: kami
 * @Date: 2022/5/19 13:30
 **/
func reverseListDfs(head *leetcode.ListNode) *leetcode.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	newHead := reverseListDfs(head.Next)
	head.Next.Next = head
	head.Next = nil

	return newHead
}

/**
 * @Description: 21. 合并两个有序链表
 * @Keyword: 双指针 1 -> 2 -> 3 -> 4
 * @Author: kami
 * @Date: 2022/5/19 17:07
 **/
func mergeTwoLists(list1 *leetcode.ListNode, list2 *leetcode.ListNode) *leetcode.ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	var dumyHead = new(leetcode.ListNode)
	if list1.Val < list2.Val {
		dumyHead.Next = list1
		list1 = list1.Next
	} else {
		dumyHead.Next = list2
		list2 = list2.Next
	}

	var preNode = dumyHead.Next
	preNode.Next = nil
	for list1 != nil || list2 != nil {
		if list1 != nil && list2 != nil {
			if list1.Val > list2.Val {
				preNode.Next = list2
				list2 = list2.Next
			} else {
				preNode.Next = list1
				list1 = list1.Next
			}
			preNode = preNode.Next
			preNode.Next = nil
		} else if list1 != nil {
			preNode.Next = list1
			break
		} else if list2 != nil {
			preNode.Next = list2
			break
		}
	}

	return dumyHead.Next
}

/**
 * @Description: 20. 有效的括号
 * @Keyword: 匹配
 * @Author: kami
 * @Date: 2022/5/21 15:42
 **/
func isValid(s string) bool {
	var seen []byte
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case '(':
			seen = append(seen, '(')
		case ')':
			if len(seen) == 0 || seen[len(seen)-1] != '(' {
				return false
			}
			seen = seen[:len(seen)-1]
		case '[':
			seen = append(seen, '[')
		case ']':
			if len(seen) == 0 || seen[len(seen)-1] != '[' {
				return false
			}
			seen = seen[:len(seen)-1]
		case '{':
			seen = append(seen, '{')
		case '}':
			if len(seen) == 0 || seen[len(seen)-1] != '{' {
				return false
			}
			seen = seen[:len(seen)-1]
		default:
			return false
		}
	}

	return len(seen) == 0
}

/**
 * @Description: 53. 最大子数组和
 * @Keyword: 维护两个最大值，1全局最大值 2局部最大值
 * @Author: kami
 * @Date: 2022/5/21 18:03
 **/
func maxSubArray(nums []int) int {
	var max = nums[0]
	var curMax = 0
	for i := 0; i < len(nums); i++ {
		if nums[i] > max {
			max = nums[i]
		}
		curMax += nums[i]
		if curMax > max {
			max = curMax
		}
		if curMax < 0 {
			curMax = 0
		}
	}
	return max
}

/**
 * @Description: 70. 爬楼梯
 * @Keyword: 典型的动态规划
 * @Author: kami
 * @Date: 2022/5/23 9:03
 **/
func climbStairs(n int) int {
	if n == 1 || n == 2 {
		return n
	}
	var dp = make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i < n+1; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

/**
 * @Description: 94. 二叉树的中序遍历 中-左-右
 * @Keyword: 首选递归，次选迭代
 * @Author: kami
 * @Date: 2022/5/23 13:19
 **/
func inorderTraversal(root *TreeNode) []int {
	// 递归方案
	return dfsInorderTraversal(root, []int{})
}

func dfsInorderTraversal(node *TreeNode, res []int) []int {
	if node == nil {
		return res
	}
	res = dfsInorderTraversal(node.Left, res)
	res = append(res, node.Val)
	res = dfsInorderTraversal(node.Right, res)
	return res
}

func recursiveInorderTraversal(root *TreeNode) (res []int) {
	stack := []*TreeNode{}
	for root != nil || len(stack) > 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, root.Val)
		root = root.Right
	}
	return

}

/**
 * @Description: 101. 对称二叉树
 * @Keyword: 左右对称
 * @Author: kami
 * @Date: 2022/5/23 14:14
 **/
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isSymmetricTwoNode(root.Left, root.Right)
}

func isSymmetricTwoNode(leftNode, rightNode *TreeNode) bool {
	if leftNode != nil && rightNode != nil {
		if leftNode.Val != rightNode.Val {
			return false
		}
		return isSymmetricTwoNode(leftNode.Left, rightNode.Right) && isSymmetricTwoNode(leftNode.Right, rightNode.Left)
	}
	if leftNode == nil && rightNode == nil {
		return true
	} else {
		return false
	}
}

/**
 * @Description: 104. 二叉树的最大深度
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/5/23 18:40
 **/
func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var max1 = 1 + maxDepth(root.Left)
	var max2 = 1 + maxDepth(root.Right)
	if max1 > max2 {
		return max1
	}
	return max2
}

/**
 * @Description: 27. 移除元素 简单
 * @Keyword: 顺序不重要
 * @Author: kami
 * @Date: 2022/5/25 12:13
 **/
func removeElement(nums []int, val int) int {
	var right = len(nums) - 1
	for i := 0; i <= right; i++ {
		if nums[i] != val {
			continue
		}
		for right > i && nums[right] == val {
			right--
		}
		nums[i] = nums[right]
		right--
	}
	return right + 1
}

/**
 * @Description: 13. 罗马数字转整数 简单
 * @Keyword: 	I             1
				VI			  4
				V             5
				XI            9
				X             10
				LX 			  40
				L             50
				CL            90
				C             100
				DC			  400
				D             500
				MD			  900
				M             1000
 * @Author: kami
 * @Date: 2022/5/26 11:43
 **/
func romanToInt(s string) int {
	var res int
	var idx int
	for idx < len(s) {
		switch {
		case s[idx] == 'M':
			res += 1000
			idx++
		case s[idx] == 'C':
			if idx < len(s)-1 {
				if s[idx+1] == 'M' {
					res += 900
					idx += 2
				} else if s[idx+1] == 'D' {
					res += 400
					idx += 2
				} else {
					res += 100
					idx++
				}
			} else {
				res += 100
				idx++
			}
		case s[idx] == 'D':
			res += 500
			idx++
		case s[idx] == 'X':
			if idx < len(s)-1 {
				if s[idx+1] == 'C' {
					res += 90
					idx += 2
				} else if s[idx+1] == 'L' {
					res += 40
					idx += 2
				} else {
					res += 10
					idx++
				}
			} else {
				res += 10
				idx++
			}
		case s[idx] == 'L':
			res += 50
			idx++
		case s[idx] == 'I':
			if idx < len(s)-1 {
				if s[idx+1] == 'X' {
					res += 9
					idx += 2
				} else if s[idx+1] == 'V' {
					res += 4
					idx += 2
				} else {
					res += 1
					idx++
				}
			} else {
				res += 1
				idx++
			}
		case s[idx] == 'V':
			res += 5
			idx++
		}
	}

	return res
}

/**
 * @Description: 58. 最后一个单词的长度 简单
 * @Keyword:
 * @Author: kami
 * @Date: 2022/5/27 7:57
 **/
func lengthOfLastWord(s string) int {
	n := len(s)
	var cnt int
	var seenLetter bool
	for i := n - 1; i >= 0; i-- {
		if s[i] == ' ' && !seenLetter {
			continue
		}
		if s[i] != ' ' {
			if !seenLetter {
				seenLetter = true
			}
			cnt++
			continue
		}
		if seenLetter && s[i] == ' ' {
			return cnt
		}
	}
	return cnt
}
